using System.Collections.Generic;

namespace System.Collections.Extended
{	
	/// <summary>
	/// Implements standard set operations as a collection. 
	/// 
	/// Sets contain only one instance of any given object, no matter how many you add to the collection.  This
	/// class differs slightly from a standard mathimatical set in that it is type-safe using Generics.  However
	/// if you want to have a set of multiple types, set <typeparamref name="T"/> to <c>object</c>. 
	/// 
	/// See http://en.wikipedia.org/wiki/Set for a more detailed description of sets
	/// </summary>
	/// <typeparam name="T">The Type of elements to store in the Set</typeparam>
	[Serializable]
	public class Set<T> : ICollection<T>
	{
		#region Fields

		/// <summary>
		/// The internal dictionary containing the set
		/// </summary>
		protected  Dictionary<T, object> _dictionary = new Dictionary<T, object>();

		/// <summary>
		/// Dummy object to add as the value for the internal dictionary.  The set is contained in the keys of the dictionary.
		/// </summary>
		protected static object _emptyObject = new object();

		/// <summary>
		/// A static reference to an empty set
		/// </summary>
		private static Set<T> _emptySet = new Set<T>();

		#endregion

		#region Constructors

		public Set()
		{
		}

		public Set(ICollection<T> collection)
		{
			AddToSet(collection);
		}

		public Set(params T[] elements)
		{
			AddToSet(elements);
		}

		#endregion

		#region Private Instance Methods

		private void AddToSet(ICollection<T> collection)
		{
			foreach (T element in collection)
			{
				try
				{
					Add(element);
				}
				catch (ArgumentException)
				{
					//Do nothing, just don't add duplicates
				}
			}
		}

		#endregion

		#region Public Static Methods

		/// <summary>
		/// Peforms a union on the two sets, leaving the original sets unchanged. Associative
		/// </summary>
		/// <param name="set1"></param>
		/// <param name="set2"></param>
		/// <returns>The union Set of the two Sets</returns>
		public static Set<T> operator | (Set<T> set1, Set<T> set2)
		{
			Set<T> resultSet = new Set<T>(set1);
			resultSet.Union(set2);
			return resultSet;
		}

		/// <summary>
		/// Performs an intersection on the two sets, leaving the original sets unchanged. Associative
		/// </summary>
		/// <param name="set1"></param>
		/// <param name="set2"></param>
		/// <returns>The intersection Set of the two Sets</returns>
		public static Set<T> operator & (Set<T> set1, Set<T> set2)
		{
			Set<T> resultSet = new Set<T>(set1);
			resultSet.Intersection(set2);
			return resultSet;
		}

		/// <summary>
		/// The relative complement of <paramref name="set2"/> in <paramref name="set1"/>. Non-associative
		/// </summary>
		/// <param name="set1"></param>
		/// <param name="set2"></param>
		/// <returns>returns the relative complement of <paramref name="set2"/> in <paramref name="set1"/></returns>
		public static Set<T> operator - (Set<T> set1, Set<T> set2)
		{
			Set<T> resultSet = new Set<T>(set1);
			resultSet.Complement(set2);
			return resultSet;			
		}

		/// <summary>
		/// Performs an XOR (exclusion) operation on <paramref name="set1"/> & <paramref name="set2"/>. 
		/// This is equivalent to <c>(this | set) - (this & set)</c>. Associative
		/// </summary>
		/// <param name="set1"></param>
		/// <param name="set2"></param>
		/// <returns>Returns a Set containing all elements that are not common to <paramref name="set1"/> & <paramref name="set2"/></returns>
		public static Set<T> operator ^ (Set<T> set1, Set<T> set2)
		{
			Set<T> resultSet = new Set<T>(set1);
			resultSet.Exclusion(set2);
			return resultSet;						
		}

		#endregion

		#region Public Instance Methods

		/// <summary>
		/// Remove all elements from the Set, leaving an empty Set
		/// </summary>
		public void Empty()
		{
			_dictionary = new Dictionary<T, object>();
		}

		/// <summary>
		/// Performs a union on the current Set with <paramref name="set"/>
		/// </summary>
		/// <param name="set">The Set to union with the current Set</param>
		public void Union(Set<T> set)
		{			
			AddToSet(set);
		}

		/// <summary>
		/// Performs an intersection on the current Set with <paramref name="set"/>
		/// </summary>
		/// <param name="set">The Set to intersect with the current Set</param>
		public void Intersection(Set<T> set)
		{
			if (!set.Equals(this))
			{
				Set<T> smallerSet = new Set<T>(Count < set.Count ? this : set);
				Set<T> largerSet = new Set<T>(Count >= set.Count ? this : set);
				Set<T> resultSet = new Set<T>();

				foreach (T element in smallerSet)
				{
					if (largerSet.Contains(element))
					{
						resultSet.Add(element);
					}
				}

				Clear();
				AddToSet(resultSet);
			}
		}

		/// <summary>
		/// Relative complement of <paramref name="set"/> in the current Set (effectively <c>this - set</c>)
		/// </summary>
		/// <param name="set"></param>
		public void Complement(Set<T> set)
		{
			if (this == set)
			{
				Empty();
			}
			else
			{
				Set<T> resultSet = new Set<T>();
				foreach (T t in this)
				{
					if (!set.Contains(t))
					{
						resultSet.Add(t);
					}
				}
				Clear();
				AddToSet(resultSet); 
			}
		}

		/// <summary>
		/// Performs and XOR operation on the current set with <paramref name="set"/>. The current set 
		/// will contain all elements that are NOT common to both sets, ie those elements that are disjoint.
		/// If both sets are equal then the current set will become the Empty Set. 		
		/// </summary>
		/// <param name="set"></param>
		public void Exclusion(Set<T> set)
		{
			if (this == set)
			{
				Empty();
			}
			else
			{
				Set<T> resultSet = new Set<T>((this | set) - (this & set));
				Empty();
				AddToSet(resultSet);
			}
		}

		/// <summary>
		/// Determinse if the current Set is a subset or proper subset of <paramref name="set"/>. 
		/// Note: The Empty Set is a subset of any other Set
		/// </summary>
		/// <param name="set"></param>
		/// <returns>Returns true if all elements of the current Set are also contained within <paramref name="set"/>; otherwise returns false.</returns>
		public bool IsSubsetOf(Set<T> set)
		{
			if (IsEmptySet || Equals(set))
			{
				return true;
			}
			else
			{
				foreach (T t in this)
				{
					if (!set.Contains(t))
					{
						return false;
					}
				}

				return true;
			}
		}

		/// <summary>
		/// Determinse if the current Set is a superset or proper superset of <paramref name="set"/>. 
		/// Note: The Empty Set is a subset of any other Set, so if <c>set.IsEmptySet == true</c> this method
		/// will return true.
		/// </summary>
		/// <param name="set"></param>
		/// <returns>Returns true if all elements of the current Set are also contained within <paramref name="set"/>; otherwise returns false.</returns>
		public bool IsSupersetOf(Set<T> set)
		{
			return set.IsSubsetOf(this);
		}

		/// <summary>
		/// Creates a comma-delimited string surrounded with braces (standard set description)
		/// </summary>
		/// <returns></returns>
		public new string ToString()
		{
			return ToString("{", "}");
		}

		/// <summary>
		/// Creates a comma-delimited string surrounded with start & end
		/// </summary>
		/// <param name="start"></param>
		/// <param name="end"></param>
		/// <returns></returns>
		public string ToString(string start, string end)
		{
			string[] keys = new string[Count];
			int x = 0;
			foreach (T element in this)
			{
				keys[x] = element.ToString();
				x++;
			}

			return string.Format("{0}{1}{2}", start, string.Join(",", keys), end);			
		}

		#endregion

		#region Public Static Properties

		/// <summary>
		/// Returns the Empty Set
		/// </summary>
		public static Set<T> EmptySet
		{
			get { return _emptySet; }
		}

		#endregion

		#region Public Instance Properties

		/// <summary>
		/// Get the cardinality (number of elements) of this Set
		/// </summary>
		public int Cardinality
		{
			get { return _dictionary.Count; }
		}

		/// <summary>
		/// Returns true if the current Set is the Empty Set
		/// </summary>
		public bool IsEmptySet
		{
			get { return (Cardinality == 0); }
		}

		#endregion

		#region ICollection<T> Members

		/// <summary>
		/// Adds an element to the Set.  Not a true set function, but exists for ease of use
		/// </summary>
		/// <param name="element">The element to add to the Set</param>
		public void Add(T element)
		{
			try
			{
				_dictionary.Add(element, _emptyObject);
			}
			catch (ArgumentException)
			{
				//Do nothing
			}
		}

		/// <summary>
		/// Synonym for <see cref="Empty"/>
		/// </summary>
		public void Clear()
		{
			Empty();
		}

		/// <summary>
		/// Determines whether the Set contains the specific element
		/// </summary>
		/// <param name="element">The element to locate in the Set</param>
		/// <returns>True if the element is found in the Set; otherwise, false</returns>
		public bool Contains(T element)
		{
			return _dictionary.ContainsKey(element);
		}

		/// <summary>
		/// Copies the elements of the Set<T> to an System.Array, starting at a particular System.Array index.
		/// </summary>
		/// <param name="array">The one-dimensional System.Array that is the destination of the elements 
		/// copied from the Set<T>. The System.Array must have zero-based indexing.</param>
		/// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
		public void CopyTo(T[] array, int arrayIndex)
		{
			_dictionary.Keys.CopyTo(array, arrayIndex);
		}

		/// <summary>
		/// Synonym of <see cref="Cardinality"/>
		/// </summary>
		public int Count
		{
			get { return Cardinality; }
		}

		/// <summary>
		/// Gets a value indicating whether the Set is read only
		/// Currently cannot be true
		/// </summary>
		public bool IsReadOnly
		{
			get { return false; }
		}

		/// <summary>
		/// Removes the element from the Set<T>. Not a true set function, but exists for ease of use
		/// </summary>
		/// <param name="element">The element to remove from the Set<T></param>
		/// <returns>true if item was successfully removed from the Set<T>; otherwise, false. This method also returns false if item is not found in the Set<T></returns>
		public bool Remove(T element)
		{
			return _dictionary.Remove(element);
		}

		#endregion

		#region IEnumerable<T> & IEnumerable Members

		/// <summary>
		/// Returns an enumerator that iterates through the collection.
		/// </summary>
		/// <returns></returns>
		public IEnumerator<T> GetEnumerator()
		{
			return _dictionary.Keys.GetEnumerator();
		}

		/// <summary>
		/// Returns an enumerator that iterates through the collection.
		/// </summary>
		/// <returns></returns>
		IEnumerator IEnumerable.GetEnumerator()
		{
			return _dictionary.Keys.GetEnumerator();
		}

		#endregion
	}
}